#include<vector>
#include<numeric>
using namespace std;
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //dp[i][j] 0~i 结果为j的选法数量
        //dp[i][j]=dp[i][j-n[i]]+dp[i][j+n[i]];
        //j:min[n]+min[target]~max[n]+max[target]
        int m=nums.size(),n=4000;
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        nums.insert(nums.begin(),0);
        dp[0][2000]=1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                if(j-nums[i]>=0&&j-nums[i]<=n)dp[i][j]+=dp[i-1][j-nums[i]];
                if(j+nums[i]>=0&&j+nums[i]<=n)dp[i][j]+=dp[i-1][j+nums[i]];
            }
        }
        return dp[m][target+2000];
    }
};
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        //简化问题分成两堆 a-b=t ,a+b=sum a=(t+sum)/2
        //dp[i][j] 0~i 结果为j的选法数量
        //dp[i][j]=dp[i-1][j]+if(j-n[i]>=0)dp[i-1][j-n[i]];
        //j:0~a
        int sum=accumulate(nums.begin(),nums.end(),0);
        int m=nums.size(),n=(sum+target)/2;
        //边界条件 a的和小于0 或者除不尽
        if((sum+target)%2||n<0)return false;
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        nums.insert(nums.begin(),0);
        //没有数 有一种选法
        dp[0][0]=1;
        for(int i=1;i<=m;i++)
            for(int j=0;j<=n;j++)
                dp[i][j]=dp[i-1][j]+((j-nums[i]>=0)?dp[i-1][j-nums[i]]:0);
        return dp[m][n];
    }
};